{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "第6章 关联分析：基本概念和算法\n",
    "\n",
    "6.1 问题定义\n",
    "\n",
    "6.1.1 基本术语\n",
    "\n",
    "事务数据集：一系列事务的集合，每个事务包含一组项。\n",
    "\n",
    "项集：包含一个或多个项的集合，如果包含k个项，则称为k项集。\n",
    "\n",
    "支持度：项集在所有事务中出现的频率。\n",
    "\n",
    "置信度：在包含X的事务中也包含Y的条件概率。\n",
    "\n",
    "6.1.2 形式化描述\n",
    "\n",
    "二元表示：事务数据可以用二元变量表示，如果项在事务中出现则为1，否则为0。\n",
    "\n",
    "项集的支持度计数：项集是事务中项的集合，支持度计数是包含特定项集的事务个数。\n",
    "\n",
    "挖掘关联规则可分解为频繁项集产生（找到满足最小支持度阈值的项集）和规则产生（从频繁项集中提取高置信度规则）两个子任务。\n",
    "\n",
    "6.2 频繁项集的产生\n",
    "\n",
    "原始方法及问题：确定格结构中每个候选项集的支持度计数，计算复杂度高，因为需要进行大量比较。\n",
    "\n",
    "先验原理：基于支持度对候选项集剪枝，若一个项集是频繁的，则其所有子集一定也是频繁的；反之，若一个项集是非频繁的，则其所有超集也一定是非频繁的。\n",
    "\n",
    "6.2.1 Apriori算法\n",
    "\n",
    "算法步骤\n",
    "\n",
    "初始将每个项视为候选 1- 项集，计算支持度得到频繁 1- 项集集合F1。\n",
    "\n",
    "用前一次迭代的频繁（k-1） - 项集产生新候选项集，计算支持度并保留频繁k项集。重复直至无新频繁项集产生。\n",
    "\n",
    "6.2.2 候选项集的产生与剪枝\n",
    "\n",
    "产生：蛮力方法：将所有k项集视为候选，再用候选剪枝去除不必要的，但其剪枝开销极大。\n",
    "\n",
    "剪枝策略:检查候选k项集的子集是否频繁，若有一个非频繁子集，则该候选被剪枝。\n",
    "\n",
    "6.2.3 支持度计数\n",
    "\n",
    "方法比较\n",
    "\n",
    "一种是将事务与所有候选项集比较更新支持度计数，计算昂贵。\n",
    "\n",
    "另一种是枚举事务包含的项集来更新对应候选项集支持度，可利用 Hash 树提高效率。\n",
    "\n",
    "6.2.4 计算复杂度\n",
    "\n",
    "影响因素\n",
    "\n",
    "支持度阈值：降低会使频繁项集增多，增加计算复杂度，频繁项集最大长度增加，扫描数据集次数增多。\n",
    "\n",
    "项数（维度）：增加需更多空间存储支持度计数，频繁项集数目增长会加大计算量和 I/O 开销。\n",
    "\n",
    "事务数：Apriori 算法反复扫描数据集，事务数增加运行时间增加。\n",
    "\n",
    "事务平均宽度：密集数据集事务平均宽度大，频繁项集最大长度增加，支持度计数时 Hash 树遍历次数增加。\n",
    "\n",
    "6.3 规则产生\n",
    "\n",
    "6.3.1 基于置信度的剪枝\n",
    "\n",
    "若规则X→Y-X不满足置信度阈值，形如X→Y-X'（X'是X子集）的规则也不满足。\n",
    "\n",
    "6.3.2 Apriori算法中规则的产生\n",
    "\n",
    "逐层方法：从后件含一个项的高置信度规则开始，用这些规则产生新候选规则。\n",
    "\n",
    "6.4 频繁项集的紧凑表示\n",
    "\n",
    "极大频繁项集：是其直接超集都不是频繁的频繁项集，可提供频繁项集的紧凑表示，能导出所有频繁项集，但不包含子集支持度信息。\n",
    "\n",
    "闭频繁项集\n",
    "\n",
    "定义与性质：闭项集是其直接超集都不具有和它相同支持度计数的项集，闭频繁项集是闭的且支持度达阈值的项集。\n",
    "作用：提供不丢失支持度信息的最小表示，可计算非闭频繁项集支持度，还可用于删除冗余关联规则。\n",
    "\n",
    "极大频繁项集与闭频繁项集的关系：极大频繁项集都是闭的。\n",
    "\n",
    "6.5 产生频繁项集的其他方法\n",
    "\n",
    "项集格遍历策略\n",
    "\n",
    "搜索策略\n",
    "\n",
    "一般到特殊与特殊到一般：Apriori 用 “一般到特殊” 策略，也可结合 “特殊到一般” 策略或双向搜索加快确定频繁项集边界。\n",
    "\n",
    "等价类：可根据项集大小、前缀或后缀划分等价类，在等价类内搜索频繁项集。\n",
    "\n",
    "宽度优先与深度优先：Apriori 采用宽度优先遍历格，深度优先从某结点开始扩展下层结点，遇非频繁结点回溯，深度优先可更快检测频繁项集边界并利用支持度剪枝。\n",
    "\n",
    "FP 增长算法\n",
    "\n",
    "FP 树表示法\n",
    "\n",
    "构造过程：读入事务构建 FP 树，先确定项支持度计数并排序，再将事务映射为树中的路径，路径可能重叠，FP 树大小与事务共享项情况和项排序有关。\n",
    "\n",
    "结构特点：包含项标记、计数和指针列表，可压缩数据，能从内存结构提取频繁项集。\n",
    "\n",
    "频繁项集产生\n",
    "\n",
    "自底向上策略：先找以特定项结尾的频繁项集，通过处理前缀路径构建条件 FP 树递归解决子问题，采用分治策略，不产生重复项集，利用支持度计数避免重复计算。\n",
    "\n",
    "6.7 关联模式的评估\n",
    "\n",
    "支持度 - 置信度框架局限性\n",
    "\n",
    "支持度可能删去潜在有意义模式，置信度忽略后件项集支持度，如 “茶→咖啡” 规则有误导性。\n",
    "\n",
    "其他客观度量\n",
    "\n",
    "兴趣因子，可比较模式频率与基线频率，但在文本挖掘领域有局限。\n",
    "\n",
    "相关分析，衡量变量相关性，但有一定局限性。\n",
    "\n",
    "IS度量，等价于余弦度量，也有类似置信度的问题。\n",
    "\n",
    "还有多种其他度量，分为对称和非对称度量，作用不同。\n",
    "\n",
    "客观度量的一致性：不同度量对关联模式定秩结果可能不同，了解差异对选择评估度量重要。\n",
    "\n",
    "缩放性：只有几率（a）在行 / 列缩放操作下不变，其他度量会变化。\n",
    "\n",
    "多个二元变量的度量\n",
    "\n",
    "部分度量可扩展到多个变量，如兴趣因子、等，也可将度量定义为项对之间关联的最值或均值，但可能无法捕获隐含联系，多维相依表分析因部分关联更复杂，可能出现辛普森悖论。\n",
    "\n",
    "辛普森悖论\n",
    "\n",
    "数据中隐藏变量可能使变量间观察到的联系消失或逆转，如购买 HDTV 和健身器的关联在分层和组合数据中结论相反，需适当分层避免虚假模式。\n",
    "\n",
    "倾斜支持度分布的影响\n",
    "\n",
    "问题描述\n",
    "\n",
    "倾斜支持度分布数据集中多数项低 / 中频率，少数项高频率，选择合适支持度阈值挖掘困难。\n",
    "\n",
    "交叉支持模式\n",
    "\n",
    "定义为支持度比率小于阈值的项集，现有度量难以消除，可通过置信度（全置信度）度量消除，其具有反单调性，能确保项集强关联，即超团模式。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3.(a)规则 Ø→A和A→ Ø的置信度是多少？\n",
    "\n",
    "任何项集与自身的支持度计数相同，所以其置信度为1。\n",
    "\n",
    "(b)令c1，c2和c3分别是规则{p}→{q}，{p}→{q，r}和{p，r}→{q}的置信度。如果假定c1，c2和c3有不同的值，那么c1,c2和c3之间可能存在什么关系？哪个规则的置信度最低？\n",
    "\n",
    "规则[p}一>q,r的置信度最低，因为它的结论比{q要多，因此在所有包含[p} 的事务中同时包含{q,r的比例可能比同时包含(q]的比例更小。\n",
    "\n",
    "\n",
    "(c)假定(b)中的规则具有相同的置信度，重复(b)的分析。哪个规则的置信度最高？\n",
    "\n",
    "在这种情况下，三个规则的置信度相同，无法确定哪个规则的置信度最高（因为它们相等）。\n",
    "\n",
    "(d)传递性：假定规则A→B和B→C的置信度都大于某个阈值minconf。规则A→C可能具有小于minconf的置信度吗？\n",
    "\n",
    "答案是可能的,传递性在概率和置信度中并不总是成立。\n",
    "\n",
    "7.考虑下面的频繁3-项集的集合：{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{2,3,4},{2,3,5},{3,4,5} 假定数据集中只有5个项。\n",
    "\n",
    "(a)列出采用Fk-1×F1，合并策略，由候选产生过程得到的所有候选4-项集。\n",
    "\n",
    "采用Fk−1×F1合并策略，由候选产生过程得到的候选 4 - 项集为： {1,2,3,4}, {1,2,3,5}, {1,2,4,5}, {1,3,4,5}, {2,3,4,5}\n",
    "\n",
    "(b)列出由Apriori 算法的候选产生过程得到的所有候选4-项集。\n",
    "\n",
    " 由 Apriori 算法的候选产生过程得到的候选 4 - 项集为： {1,2,3,4}, {1,2,3,5}, {1,2,4,5}, {1,3,4,5}, {2,3,4,5}\n",
    "\n",
    "(c)列出Apriori 算法候选剪枝步骤后剩下的所有候选4-项集。\n",
    "\n",
    "假设经过检查，所有上述得到的候选 4 - 项集的真子集都是频繁的，那么剩下的候选 4 - 项集就是{1,2,3,4}, {1,2,3,5}, {1,2,4,5}, {1,3,4,5}, {2,3,4,5}。因为在这个数据集中，所有的 3 - 项集都是频繁的，所以根据 Apriori 算法的先验原理，由这些频繁 3 - 项集合并得到的候选 4 - 项集在剪枝步骤中都得以保留（因为它们的子集都是频繁的）。\n",
    "\n",
    "9.Apriori算法使用Hash树数据结构，有效地计算候选项集的支持度。考虑图6-32所示的候选3-项集的Hash树。\n",
    "\n",
    "(a)给定一个包含项{1,3,4,5,8}的事务，在寻找该事务的候选项集时，访问了Hash树的哪些叶结点？\n",
    "\n",
    "最终访问的叶结点为 ：L1,L5,L6,L9,L11\n",
    "\n",
    "(b)使用(a)中访问的叶结点确定事务{1,3,4,5,8}包含的候选项集。\n",
    "\n",
    "事务 {1,3,4,5,8} 包含的候选项集有 {1,3,4}、{1,3,5}、{1,4,5}、{3,4,5}。\n",
    "\n",
    "11.给定图6-33所示的格结构和表6-24给定的事务，用如下字母标记每一个结点。\n",
    "\n",
    "M：如果结点是极大频繁项集。\n",
    "\n",
    "C：如果结点是闭频繁项集。\n",
    "\n",
    "N：如果结点是频繁的，但既不是极大的也不是闭的。\n",
    "\n",
    "I：如果结点是非频繁的。\n",
    "\n",
    "假定支持度阈值等于30%。\n",
    "\n",
    "M（极大频繁项集）：{abd},{bde}\n",
    "C（闭频繁项集）：{b},{d},{bd},{bde}\n",
    "N（频繁但既不是极大也不是闭的）：{ab},{be},{cd},{de}\n",
    "I（非频繁的）：\n",
    "\n",
    "19.考虑表6-27中显示的相依表。\n",
    "\n",
    "(a)对于表Ⅰ，计算关联模式{A，B}的支持度、兴趣度和Ø相关系数，并计算规则A→B和B→A的置信度。\n",
    "\n",
    "对于表I:\n",
    "\n",
    "关联模式{A，B}的支持度=0.89\n",
    "\n",
    "兴趣度式=1\n",
    "\n",
    "φ相关系数=0\n",
    "\n",
    "规则A→B的置信度=0.5\n",
    "\n",
    "规则B→A的置信度=0.5\n",
    "\n",
    "(b)对于表Ⅱ，计算关联模式{A，B}的支持度、兴趣度和Ø相关系数，并计算规则A→B和B→A的置信度。\n",
    "\n",
    "对于表II:\n",
    "\n",
    "\n",
    "关联模式{A，B}的支持度=0.99\n",
    "\n",
    "兴趣度=0.99\n",
    "\n",
    "φ相关系数置=0\n",
    "\n",
    "规则A→B的置信度=0.99\n",
    "\n",
    "规则B→A的置信度=0.99\n",
    "\n",
    "(c)由(a)和(b)的结果可以得出什么结论？\n",
    "\n",
    "这表明在表II中A和B的关联性更强，即当A出现时,B出现的概率更高，反之亦然。这进一步说明在分析关联模式时，需要综合考虑多种度量指标，不能仅依赖单一指标来判断变量之间的关系。\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.11.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
